package com.hexm.sudokuweb.sudoku.app;

import com.hexm.sudokuweb.sudoku.domain.SudokuDo;
import com.hexm.sudokuweb.sudoku.util.SudokuUtil;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Calendar;
import java.util.List;

/**
 * @Classname SudokuDoService
 * @Description TODO
 * @Date 2021/2/12 23:13
 * @Created by hexm
 */
public class SudokuDoService {

    private List<int[][]> resultList = new ArrayList<>();

    private long recursionCount; //递归执行次数

    public long getRecursionCount() {
        return recursionCount;
    }

    public List<int[][]> getResultList() {
        return resultList;
    }

    private void addResultNoRepeat(int[][] result) {
        boolean exist = false;
        for (int[][] data : resultList) {
            if (SudokuUtil.arrayEquals(data, result)) {
                exist = true;
            }
        }
        if (!exist) {
            resultList.add(result);
        }
    }

    /**
     * 计算数独
     *
     * @param param
     * @return
     */
    public void calculate(int[][] param) throws Exception {
        recursionCount++;
        if (param.length < 9) {
            throw new Exception("parma invalid.");
        }
//        // 有答案后截断所有递归
//        if(resultList.size() > 0) {
//            return;
//        }
        SudokuDo sudokuDo = new SudokuDo(param);
        // 填充easy数字
//        sudokuDo.fillEasyDigit();
        // 是否合法
        if (!sudokuDo.isValid()) {
            return;
        }

        if (sudokuDo.isFullOk()) {
            addResultNoRepeat(param);
            return;
        }
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (param[i][j] == 0) {
                    for (int k = 1; k <= 9; k++) {
                        int[][] array = SudokuUtil.dataCopy(sudokuDo.getSudokuData());
//                        int[][] array = SudokuUtil.dataCopy(param); //会导致大量递归
//                        int[][] array = SudokuUtil.dataCopy(currentData);
                        array[i][j] = k;
                        sudokuDo = new SudokuDo(array);
                        if (sudokuDo.isValid()) {
                            // 填充easy数字
                            int[][] arrayTemp = SudokuUtil.dataCopy(array);
                            SudokuDo sudokuDoTemp = new SudokuDo(arrayTemp);
                            sudokuDoTemp.fillEasyDigit();
                            if(sudokuDoTemp.isValid()) {
                                array = sudokuDoTemp.getSudokuData();
                            }
//                            array = SudokuUtil.dataCopy(sudokuDoNew.getSudokuData());
//                            SudokuUtil.print(sudokuDoTemp.getSudokuData());
//                            System.out.println("---------------------------------------");
                            calculate(array);
                        }
                    }
                }
            }
        }
    }


    /**
     * 测试样例
     * 1 4 5 3 2 7 6 9 8
     * 8 3 9 6 5 4 1 2 7
     * 6 7 2 9 1 8 5 4 3
     * 4 9 6 1 8 5 3 7 2
     * 2 1 8 4 7 3 9 5 6
     * 7 5 3 2 9 6 4 8 1
     * 3 6 7 5 4 2 8 1 9
     * 9 8 4 7 6 1 2 3 5
     * 5 2 1 8 3 9 7 6 4
     *
     * @param args
     * @throws Exception
     */
    public static void main(String[] args) throws Exception {
        SudokuDoService sudokuDoService = new SudokuDoService();
        int[][] ints = new int[9][9];
        // 基本测试
//        ints[0] = new int[]{1, 4, 5, 3, 2, 7, 6, 9, 8};
//        ints[1] = new int[]{8, 3, 9, 6, 5, 4, 1, 0, 7};
//        ints[2] = new int[]{6, 7, 2, 9, 1, 8, 5, 0, 3};
//        ints[3] = new int[]{4, 9, 6, 1, 8, 5, 3, 7, 2};
//        ints[4] = new int[]{2, 1, 8, 4, 7, 3, 9, 5, 6};
//        ints[5] = new int[]{7, 5, 3, 2, 9, 6, 4, 8, 1};
//        ints[6] = new int[]{3, 6, 7, 5, 4, 2, 8, 1, 9};
//        ints[7] = new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0};
//        ints[8] = new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0};
        // https://blog.csdn.net/stereohomology/article/details/47071233?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-3.control&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-3.control
        ints[0] = new int[]{0, 9, 0, 1, 0, 0, 5, 0, 0};
        ints[1] = new int[]{0, 0, 0, 0, 7, 9, 8, 0, 1};
        ints[2] = new int[]{2, 0, 0, 0, 0, 0, 0, 0, 6};
        ints[3] = new int[]{0, 3, 0, 0, 0, 0, 0, 0, 0};
        ints[4] = new int[]{0, 0, 0, 7, 8, 1, 0, 0, 0};
        ints[5] = new int[]{0, 0, 4, 0, 0, 0, 0, 2, 0};
        ints[6] = new int[]{7, 0, 0, 6, 0, 0, 0, 0, 4};
        ints[7] = new int[]{6, 0, 1, 5, 3, 0, 0, 0, 0};
        ints[8] = new int[]{0, 0, 9, 0, 0, 7, 0, 6, 0};
//        // 第9题
//        ints[0] = new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0};
//        ints[1] = new int[]{2, 4, 1, 8, 0, 0, 6, 7, 0};
//        ints[2] = new int[]{0, 0, 5, 4, 1, 0, 2, 8, 0};
//        ints[3] = new int[]{0, 0, 4, 0, 6, 0, 8, 0, 7};
//        ints[4] = new int[]{0, 0, 0, 0, 0, 0, 0, 5, 6};
//        ints[5] = new int[]{0, 8, 0, 0, 7, 0, 0, 2, 3};
//        ints[6] = new int[]{6, 1, 0, 0, 5, 0, 0, 9, 0};
//        ints[7] = new int[]{0, 5, 3, 0, 9, 1, 0, 0, 8};
//        ints[8] = new int[]{0, 0, 9, 0, 8, 0, 0, 0, 0};
//        // 第10题
//        ints[0] = new int[]{8, 5, 6, 1, 9, 0, 0, 0, 0};
//        ints[1] = new int[]{1, 4, 0, 5, 2, 0, 0, 0, 0};
//        ints[2] = new int[]{3, 0, 0, 0, 7, 0, 4, 5, 0};
//        ints[3] = new int[]{0, 0, 2, 0, 0, 8, 3, 7, 0};
//        ints[4] = new int[]{0, 0, 0, 0, 5, 0, 0, 1, 9};
//        ints[5] = new int[]{0, 9, 0, 0, 0, 0, 0, 0, 0};
//        ints[6] = new int[]{0, 0, 1, 7, 0, 0, 0, 8, 0};
//        ints[7] = new int[]{2, 0, 4, 6, 0, 5, 0, 0, 7};
//        ints[8] = new int[]{5, 0, 3, 0, 0, 0, 0, 0, 0};
        // 第124题
//        ints[0] = new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0};
//        ints[1] = new int[]{0, 0, 3, 4, 0, 1, 2, 0, 0};
//        ints[2] = new int[]{0, 7, 0, 0, 9, 0, 0, 3, 0};
//        ints[3] = new int[]{0, 0, 6, 7, 0, 8, 9, 0, 0};
//        ints[4] = new int[]{0, 2, 0, 0, 0, 0, 0, 5, 0};
//        ints[5] = new int[]{0, 0, 1, 2, 0, 3, 4, 0, 0};
//        ints[6] = new int[]{0, 9, 0, 0, 6, 0, 0, 7, 0};
//        ints[7] = new int[]{0, 0, 2, 1, 0, 4, 3, 0, 0};
//        ints[8] = new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0};
        long t1 = System.currentTimeMillis();
        sudokuDoService.calculate(ints);
        long t2 = System.currentTimeMillis();
        Calendar c = Calendar.getInstance();
        c.setTimeInMillis(t2 - t1);
//        SudokuDo sudokuDo = new SudokuDo(ints);
        if (sudokuDoService.getResultList().size() > 0) {
            for (int[][] result : sudokuDoService.getResultList()) {
                SudokuDo sudokuDo = new SudokuDo(result);
                SudokuUtil.print(sudokuDo.getSudokuData());
                System.out.println("//////////////////////////////////////////////////////");
            }
        }
        System.out.println("耗时: " + c.get(Calendar.MINUTE) + "分 " + c.get(Calendar.SECOND) + "秒 " + c.get(Calendar.MILLISECOND) + " 毫秒");
        System.out.println("递归次数：" + sudokuDoService.getRecursionCount());
        System.out.println("find result! " + sudokuDoService.getResultList().size());
    }
}
